package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;

class InsertionSortList {
    // 2023-05-04 10:25:24
    public static void main(String[] args) {
        Solution solution = new InsertionSortList().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;

            ListNode index = head.next;
            ListNode sorted = head;
            while (index != null) {
                if (sorted.val <= index.val) {
                    sorted = sorted.next;
                } else {
                    // 遍历已经排好序的元素，找到正确的位置
                    ListNode prev = dummyHead;
                    while (prev.next.val <= index.val) {
                        prev = prev.next;
                    }
                    // 在后面插入元素
                    sorted.next = index.next;
                    index.next = prev.next;
                    prev.next = index;
                }
                index = sorted.next;
            }
            return dummyHead.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}